The spread of personal computers and workstations has led to the development of networks for interconnecting such equipment and common resources such as printers and data storage devices. More powerful and sophisticated computing equipment and programs have progressively become available, allowing the processing of data in larger and larger quantities, for example in the form of database information and graphic images. These developments have in turn placed increasing demands on the speed and capacity of networks.
Various new networking technologies have been proposed to cater for these demands. One recent proposal has been established as IEEE Standard 802.12, and is also known as 100VG-AnyLAN. This technology, which transfers data at 100 megabits/s (Mb/s), involves splitting a data frame to be transmitted into consecutive blocks of five bits each, encoding the blocks using a 5B6B code, distributing the encoded blocks among four twisted-pair conductors, and applying a cyclic redundancy check (CRC) code to each of the encoders's output bit streams, using the same CRC generator polynomial for each of the bit streams.
Although networks based on this technology are being deployed and meet current requirements, it is envisaged that future computing developments will eventually require even higher-speed and thus higher-capacity networks. Such higher-speed networks will also require that several channels be used in parallel. Moreover, the high speed will bring with it further needs for efficient error detection.
There are two kinds of errors which may corrupt data during transmission. The first kind is random errors due to, for example, thermal noise. These may corrupt any bit on any channel and anywhere in the packet with (in general) equal probability, but are usually rare enough that there is a negligible probability of there being a large number of symbols corrupted in this way in the same packet. The second kind is errors due, for example, to temporary interference by nearby electrical equipment. These errors are correlated in time; if a symbol on one channel is corrupted by such an error, a symbol sent on a parallel channel at the same time is more likely to be corrupted by a `correlated` error than a symbol sent at a different time. A particular kind of correlated error is the `burst` error, which is a correlated error limited in duration.
Standard design of CRC codes involves choosing a generator polynomial which:
has large order, so as to detect error patterns which are restricted in duration; PA0 has large Hamming distance, so as to detect error patterns caused by thermal noise; and PA0 is divisible by the polynomial (x-1), which acts as a parity check in the case where the signals are binary, and which has similar useful properties in the case of non-binary signals provided that the generator polynomial is also carefully chosen. PA0 it may be possible to implement CRCs of length b using standard circuit designs when this is not possible for CRCs of the longer length m.b, so the cost of implementation may be smaller; PA0 the m checksums can be transmitted and processed in parallel and hence the time overhead for error detection may be reduced; and PA0 in general it is easier to find CRCs with good detection properties of shorter lengths.
The longer the CRC code or checksum, the larger the burst it is guaranteed to detect, but the longer the time spent calculating, transmitting, and checking the checksum.
Systems currently in use either use a CRC on the entire data stream, or (as in the case of 100VG-AnyLAN) apply a checksum to each channel, using the same generator polynomial for all channels. Applying m checksums each of length b symbols to m channels sending data in parallel provides similar (though in general not identical) capabilities for detecting thermal noise errors to applying a single checksum of length m.b to the data. The advantages of using m checksums in parallel are:
A disadvantage is that in general the burst error detection capabilities of m checksums of length b in parallel are not as good as the burst error detection capabilities of a single checksum of length m.b.
Furthermore, there has hitherto been no known way of constructing CRC polynomials with desirable properties of detecting more general correlated errors.
It is an object of this invention to provide a system and method for communicating data over multiple channels, which has improved capabilities in detecting correlated errors without requiring a large time overhead or specialized hardware for computing checksums of long length. It is a further object of the invention to provide a method of constructing CRC polynomials which assists in enabling these capabilities to be obtained.